package minFallingPathSum

/**
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

*/
func minFallingPathSum(matrix [][]int) int {
	ans := 6666666 //根据题目给出的数据范围确定一个初始值
	m := len(matrix)
	n := len(matrix[0])
	memo := make([][]int, m) // 备忘录
	for i := 0; i < m; i++ {
		memo[i] = make([]int, n)
	}
	// 定义dp函数： 从第一排dp[0][j] 到dp[i][j]的最短下落路径
	var dp func(matrix [][]int, i, j int) int

	dp = func(matrix [][]int, i, j int) int {
		if i >= m || j >= n || i < 0 || j < 0 {
			return 6666666
		}
		if i == 0 {
			return matrix[0][j]
		}
		if memo[i][j] != 0 {
			return memo[i][j]
		}
		// 因为memo[i][j] 是当前 matrix[i][j] 加上 matrix[i-1][j-1]  matrix[i-1][j]  matrix[i-1][j+1]的最小值
		// 三叉树的后序遍历
		memo[i][j] = matrix[i][j] + min3(
			dp(matrix, i-1, j-1),
			dp(matrix, i-1, j),
			dp(matrix, i-1, j+1),
		)
		return memo[i][j]
	}

	for i := 0; i < n; i++ {
		// 正确答案位于最后一排上
		ans = min(ans, dp(matrix, m-1, i))
	}
	return ans
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

func min3(a, b, c int) int {
	return min(a, min(b, c))
}
